package heap

import (
	"gitee.com/kklt1996/data-structure/array"
)

/*
	创建一个默认容量的最大堆
*/
func CreateMaxHeapDefault(comparator func(thisValue interface{}, compareValue interface{}) int) MaxHeap {
	arrayDefault := array.CreateSliceArrayDefault()
	return MaxHeap{data: arrayDefault, comparator: comparator}
}

/*
	创建一个指定容量的最大堆
*/
func CreateMaxHeap(comparator func(thisValue interface{}, compareValue interface{}) int, capacity int) MaxHeap {
	sliceArray := array.CreateSliceArray(0, capacity)
	return MaxHeap{data: sliceArray, comparator: comparator}
}

/*
	O(n)
	根据slice创建最大堆
	使用heapify的方式将slice转换为最大堆
*/
func CreateMaxHeapFromSliceArray(comparator func(thisValue interface{}, compareValue interface{}) int, sourceSlice array.SliceArray) MaxHeap {
	sliceArray := array.CreateSliceArray(0, len(sourceSlice)+1)
	// 将元素进行复制
	for _, v := range sourceSlice {
		sliceArray.AddLast(v)
	}
	maxHeap := MaxHeap{data: sliceArray, comparator: comparator}
	// 从最后一个非叶子节点开始左siftDown操作
	for i := maxHeap.parentIndex(len(*sliceArray) - 1); i >= 0; i-- {
		maxHeap.siftDown(i)
	}
	return maxHeap
}

/*
	创建一个默认容量的最小堆
*/
func CreateMinHeapDefault(comparator func(thisValue interface{}, compareValue interface{}) int) MinHeap {
	arrayDefault := array.CreateSliceArrayDefault()
	return MinHeap{data: arrayDefault, comparator: comparator}
}

/*
	创建一个指定容量的最小堆
*/
func CreateMinHeap(comparator func(thisValue interface{}, compareValue interface{}) int, capacity int) MinHeap {
	sliceArray := array.CreateSliceArray(0, capacity)
	return MinHeap{data: sliceArray, comparator: comparator}
}

/*
	O(n)
	使用heapify的方式将slice转换为最小堆
*/
func CreateMinHeapFromSliceArray(comparator func(thisValue interface{}, compareValue interface{}) int, sourceSlice array.SliceArray) MinHeap {
	sliceArray := array.CreateSliceArray(0, len(sourceSlice)+1)
	// 将元素进行复制
	for _, v := range sourceSlice {
		sliceArray.AddLast(v)
	}
	maxHeap := MinHeap{data: sliceArray, comparator: comparator}
	// 从最后一个非叶子节点开始左siftDown操作
	for i := maxHeap.parentIndex(len(*sliceArray) - 1); i >= 0; i-- {
		maxHeap.siftDown(i)
	}
	return maxHeap
}

type Heap interface {
	GetSize() int

	IsEmpty() bool

	Add(value interface{})

	FindTop() (interface{}, error)

	ExtractTop() (interface{}, error)

	Replace(value interface{}) (interface{}, error)
}
